{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #古董键盘"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming #combinatorics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划 #组合数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: keyboard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #古董键盘"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "小扣在秋日市集购买了一个古董键盘。由于古董键盘年久失修，键盘上只有 26 个字母 **a~z** 可以按下，且每个字母最多仅能被按 `k` 次。\n",
    "\n",
    "小扣随机按了 `n` 次按键，请返回小扣总共有可能按出多少种内容。由于数字较大，最终答案需要对 1000000007 (1e9 + 7) 取模。\n",
    "\n",
    "\n",
    "**示例 1：**\n",
    ">输入：`k = 1, n = 1`\n",
    "> \n",
    ">输出：`26`\n",
    "> \n",
    ">解释：由于只能按一次按键，所有可能的字符串为 \"a\", \"b\", ... \"z\" \n",
    "\n",
    "**示例 2：**\n",
    ">输入：`k = 1, n = 2`\n",
    "> \n",
    ">输出：`650`\n",
    "> \n",
    ">解释：由于只能按两次按键，且每个键最多只能按一次，所有可能的字符串（按字典序排序）为 \"ab\", \"ac\", ... \"zy\" \n",
    "\n",
    "**提示：**\n",
    "- `1 <= k <= 5`\n",
    "- `1 <= n <= 26*k`\n",
    " \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [Uh984O](https://leetcode.cn/problems/Uh984O/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [Uh984O](https://leetcode.cn/problems/Uh984O/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1\\n1', '1\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def keyboard(self, k: int, n: int) -> int:\n",
    "        f = [[0] * 27 for _ in range(n + 1)]\n",
    "        for j in range(27):\n",
    "            f[0][j] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, 27):\n",
    "                for t in range(min(k, i) + 1):\n",
    "                    f[i][j] += f[i - t][j - 1] * self.c(i, t)\n",
    "                f[i][j] %= 1000000007\n",
    "        return f[n][26]\n",
    "\n",
    "    def c(self, n: int, k: int) -> int:\n",
    "        result = 1\n",
    "        for i in range(1, k + 1):\n",
    "            result = result * (n - i + 1) // i\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def keyboard(self, k: int, n: int) -> int:\n",
    "        C = [[0 for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "        C[0][0] = 1 \n",
    "        for i in range(1, n + 1):\n",
    "            C[i][0] = 1 \n",
    "            for j in range(1, k + 1):\n",
    "                C[i][j] = C[i - 1][j - 1] + C[i - 1][j]\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = 1 \n",
    "        for i in range(1, 27):\n",
    "            new = [0] * (n + 1)\n",
    "            new[0] = 1 \n",
    "            for cur in range(1, n + 1):\n",
    "                for p in range(min(k + 1, cur + 1)):\n",
    "                    new[cur] += dp[cur - p] * C[cur][p]\n",
    "                    new[cur] %= 10 ** 9 + 7 \n",
    "            dp = new \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def keyboard(self, k: int, n: int) -> int:\n",
    "        mod = 1000000007\n",
    "        # 初始化dp数组\n",
    "        dp = [[0] * 27 for _ in range(n + 1)]\n",
    "        \n",
    "        # 设置初始状态\n",
    "        for i in range(27):\n",
    "            dp[0][i] = 1\n",
    "        \n",
    "        # 填充dp数组\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, 27):\n",
    "                for x in range(k + 1):\n",
    "                    if i - x >= 0:\n",
    "                        dp[i][j] += dp[i-x][j-1] * self.C(i, x)\n",
    "                        dp[i][j] %= mod\n",
    "        \n",
    "        return dp[n][26]\n",
    "\n",
    "    # 计算组合数\n",
    "    def C(self, m: int, n: int) -> int:\n",
    "        k = 1\n",
    "        ans = 1\n",
    "        while k <= n:\n",
    "            ans = ((m - k + 1) * ans) // k\n",
    "            k += 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "排列问题\n",
    "'''\n",
    "import math\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def keyboard(self, k: int, n: int) -> int:\n",
    "        MOD = 1000000007\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(c: int, n: int, k: int) -> int:\n",
    "            if n == 0:\n",
    "                return 1\n",
    "            if c <= 0:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for i in range(0, min(n, k) + 1):\n",
    "                res += math.comb(n, i) * dfs(c-1, n - i, k) % MOD\n",
    "            return res % MOD\n",
    "\n",
    "        ans = dfs(26, n, k)\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def keyboard(self, k: int, n: int) -> int:\n",
    "        mod=1000000007\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(c,n,k):\n",
    "            if n==0:\n",
    "                return 1\n",
    "            if c<=0:\n",
    "                return 0\n",
    "            res=0\n",
    "            for i in range(0,min(n,k)+1):\n",
    "                res += math.comb(n,i)*dfs(c-1,n-i,k)%mod\n",
    "            return res%mod\n",
    "        res=dfs(26,n,k)\n",
    "        return res%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import math\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def keyboard(self, k: int, n: int) -> int:\n",
    "        MOD = 1000000007\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(c, n, k):\n",
    "            if n == 0:\n",
    "                return 1\n",
    "            if c <= 0:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for i in range(0, min(n, k) + 1):\n",
    "                res += math.comb(n, i)*dfs(c-1, n - i, k) % MOD\n",
    "            return res % MOD\n",
    "\n",
    "        ans = dfs(26, n, k)\n",
    "        return ans % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import math\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def keyboard(self, k: int, n: int) -> int:\n",
    "        MOD = 1000000007\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(c, n, k):\n",
    "            if n == 0:\n",
    "                return 1\n",
    "            if c <= 0:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for i in range(0, min(n, k) + 1):\n",
    "                res += math.comb(n, i)*dfs(c-1, n - i, k) % MOD\n",
    "            return res % MOD\n",
    "\n",
    "        ans = dfs(26, n, k)\n",
    "        return ans % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def keyboard(self, k: int, n: int) -> int:\n",
    "        mod = 10**9 + 7 \n",
    "        @cache \n",
    "        def f(j, res):\n",
    "            if j>26:\n",
    "                if res==0:\n",
    "                    return 1 \n",
    "                return 0 \n",
    "            if res==0:\n",
    "                return 1 \n",
    "            ans = 0\n",
    "            for i in range(k + 1):\n",
    "                if i<=res:\n",
    "                    ans += f(j+1, res - i)*math.comb(res, i)\n",
    "                else:\n",
    "                    break \n",
    "            return ans%mod \n",
    "        return f(1, n)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "排列问题\n",
    "'''\n",
    "import math\n",
    "import functools\n",
    "\n",
    "class Solution:\n",
    "    def keyboard(self, k: int, n: int) -> int:\n",
    "        MOD = 1000000007\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(c, n, k):\n",
    "            if n == 0:\n",
    "                return 1\n",
    "            if c <= 0:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for i in range(0, min(n, k) + 1):\n",
    "                res += math.comb(n, i)*dfs(c-1, n - i, k) % MOD\n",
    "            return res % MOD\n",
    "\n",
    "        ans = dfs(26, n, k)\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def keyboard(self, k: int, n: int) -> int:\n",
    "        @ cache\n",
    "        def dfs(a, nd):\n",
    "            if nd < 0:\n",
    "                return 0\n",
    "            if a == 0:\n",
    "                return 1 if nd == 0 else 0\n",
    "            ans = 0\n",
    "            for i in range(k + 1):\n",
    "                ans += comb(nd, i) * dfs(a - 1, nd - i)\n",
    "                ans %= mod\n",
    "            return ans\n",
    "\n",
    "        comb = cache(math.comb)\n",
    "        mod = 10 ** 9 + 7\n",
    "        return dfs(26, n)\n",
    "                "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
